package gsw.tool.arithmetic;

import java.util.Arrays;

import gsw.tool.common.Tool;
import gsw.tool.common.ToolShow;

/**
 * 减治法是每一步都能缩小一定的问题规模（-1，-k，-n/2等），最后变成1个最小的小问题。
 */
public class ReduceConquer {
    public static void test() {
        //测试堆排序
        Integer[] arr = new Integer[]{77, 112, 24, 66, 77, 99, 32, 88};
        Integer[] result = heapSort(arr);
        ToolShow.printArr(result);

        //测试深度优先查找
        int[][] arr2 = new int[8][18];
        arr2[0] = new int[]{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
        arr2[1] = new int[]{3, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 3, 3, 0, 3, 3};
        arr2[2] = new int[]{3, 3, 3, 0, 3, 3, 3, 0, 3, 3, 0, 3, 0, 0, 0, 0, 3, 3};
        arr2[3] = new int[]{3, 3, 3, 0, 3, 3, 3, 0, 0, 0, 0, 3, 0, 3, 3, 3, 3, 3};
        arr2[4] = new int[]{3, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 0, 0, 0, 3, 3, 3};
        arr2[5] = new int[]{3, 0, 3, 3, 3, 0, 0, 0, 0, 0, 3, 0, 3, 3, 0, 0, 0, 3};
        arr2[6] = new int[]{3, 0, 0, 3, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3, 3, 3, 0, 3};
        arr2[7] = new int[]{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
        dfsSort(arr2, 1, 1, 6, 16);
        ToolShow.printArr(arr2);
    }

    /**
     * 堆排序:基于完全二叉树的升序排序。
     * 堆排序的过程：
     * 1. 将线性结构(比如数组)当作完全二叉树来排序：如果数组中一个元素A的下标为k，那么下标为(k-1)/2的元素相当于A的父节点，下标为2k+1的元素相当于A的左子节点，下标为2k+2的元素相当于A的右子节点；
     * 2. 对n个元素进行排序，将最小值放到数组的首位：先把节点k的左子树的最小值放到k的左子节点，再把先把节点k的右子树的最小值放到k的右子节点，然后节点k与其左右子节点的最小值即为数组的最小值。这里需要使用递归。
     * 3. 取出数组的最小值，放入数组M；
     * 4. 令n=n-1，重复步骤2、3，直到n=0,排序完成：M即为拍好序的数组。
     * 应用：当数据源为无序或链式结构的时候，进行二分查找。一般不用于排序，空间复杂度太高。
     */
    public static <E extends Comparable<E>> E[] heapSort(E[] arr) {
        if (Tool.isEmpty(arr)) {
            return null;
        }

        //由于直接new泛型数组报错，所以使用Arrays.copyOf()
        E[] result = Arrays.copyOf(arr, arr.length);
        //缩小问题规模：每次-1
        for (int i = 0; i < arr.length; i++) {
            // 缩小后的问题规模
            int n = arr.length - i;
            // 解决小问题：对首位进行单次堆排序，将最小值放到首位
            heapSort(arr, n, 0);
            // 获取最小值
            result[i] = arr[0];
            // 将未排序的数据放到首位
            arr[0] = arr[n - 1];
        }

        return result;
    }

    /**
     * 单次堆排序：递归设置当前节点与其左右节点的最小值
     *
     * @param arr 要排序的数组
     * @param n   表示数组大小，即问题的规模
     * @param k   要比较的节点下标
     */
    public static <E extends Comparable<E>> void heapSort(E[] arr, int n, int k) {
        // 左节点下标
        int left = 2 * k + 1;
        // 右节点下标
        int right = 2 * k + 2;
        if (left >= n) {
            return;
        }

        // 将左子树中最小值放到左节点
        heapSort(arr, n, left);
        // 再将右子树中最小值放到右节点
        heapSort(arr, n, right);

        E data = arr[k];
        E l = arr[left];
        //右节点如果不存在，就将它的值设为MAX
        E r = right < n ? arr[right] : null;
        //如果当前节点是最小的，直接返回
        if (data.compareTo(l) <= 0 && (r == null || data.compareTo(r) <= 0)) {
            return;
        }
        //如果左节点是最小的，就将左节点与当前节点交换
        if (r == null || l.compareTo(r) < 0) {
            arr[left] = data;
            arr[k] = l;
            //如果右节点是最小的，就将右节点与当前节点交换
        } else {
            arr[right] = data;
            arr[k] = r;
        }
    }

    /**
     * 深度优先查找是优先按纵深查找的思想，按照一个方向一直走，没有了路就回退，然后换方向找，知道找到终点。
     * 操作步骤：
     * 1. 用一个二维数组模拟迷宫，数组的值：0表示走得通，1表示走不通，2表示走过，3表示墙。并指定起点和终点；
     * 2. 从起点开始，按左下右上的顺序查找，如果能走到下一个点，就将它的值标记为2，然后以这个点为新的起点开始，按左下右上的顺序查找；如果不能走到下一个点，就将它的值标记为1，然后回退到上一个点，从剩下的方向查找；
     * 3. 重复步骤2，知道走到终点。
     * 应用：迷宫找路
     *
     * @param arr    需要查找的数组。其中0表示走得通，1表示走不通，2表示走过，3表示墙。
     * @param startX 起点横坐标
     * @param startY 起点纵坐标
     * @param endX   终点横坐标
     * @param endY   终点纵坐标
     */
    public static boolean dfsSort(int[][] arr, int startX, int startY, int endX, int endY) {
        if (startX < 0 || startY < 0 || endX < 0 || endY < 0) {
            return false;
        }
        // 到达终点
        if (arr[endX][endY] == 2) {
            return true;
        }

        //如果没有走过，就按左下右上的顺序查找
        if (arr[startX][startY] == 0) {
            //标记已走过
            arr[startX][startY] = 2;
            //从左边开始找
            if (dfsSort(arr, startX - 1, startY, endX, endY)) {
                return true;
                //从上边开始找
            } else if (dfsSort(arr, startX, startY - 1, endX, endY)) {
                return true;
                //从右边开始找
            } else if (dfsSort(arr, startX + 1, startY, endX, endY)) {
                return true;
                //从下边开始找
            } else if (dfsSort(arr, startX, startY + 1, endX, endY)) {
                return true;
                //如果没有路，就标记为1，然后返回
            } else {
                arr[startX][startY] = 1;
                return false;
            }
        }
        return false;
    }
}
